Data storage systems such as disc drives typically store information on the surface of a storage media such as a magnetic or optical disc. In a typical disc drive a number of discs are stacked in a disc stack and mounted together on a single spindle that rotates. Each side of the disc in the disc stack has a surface which is used to store information. Above the surface of the disc is usually at least one head that reads information from and/or writes information to the surface of the disc. These heads are typically mounted on an actuator arm that moves the heads in tandem over the surface of the discs so that all of the heads at the same approximate disc radius at the same time.
When information is stored on a disc it is generally stored in a set of concentric circular patterns called tracks. The tracks on the disc surface are typically divided into sectors. Sectors are the basic unit of data storage on a disc surface. A sector is a “pie-shaped” angular section of a track that is bounded on two sides by radii of the disc and on the other side by the perimeter of the circle that defines the track. In other words, the sector is a small segment along the length of a track. In previous generation hard discs, each disc has the same number of sectors per track, and the number of sectors per track was generally the same regardless of the disc's manufacturer. However, advances in disc drive design have allowed the number of sectors per track to vary significantly within the disc and across manufacturers.
In order to read and write data from the correct location in the disc stack, the data storage areas of the disc stack are identified by a cylinder address, head address and sector address. A cylinder identifies a set of specific tracks on the disc surfaces in the disc stack which lie at equal radii and are, in general, simultaneously accessible by the collection of heads. The head address identifies which head can read the data and therefore identifies the disc in the stack that the data is located. Each track within a cylinder is further divided into sectors for storing data and servo information. The sector is identified by an associated sector address.
Most cylinders are available for read/write access by the host computer. However, drive unique information, for example, the drive defect table (a table that contains remap information to circumvent defective sectors formed at the time the disc was manufactured) is stored in reserved cylinders which are not normally accessible by the host computer. Typically, multiple copies of drive unique information are stored in reserved cylinders. Additionally, multiple copies of user data are sometimes stored on user accessible cylinders for faster access and data backup purposes.
Each of the multiple copies of data is stored on a different set of sectors. Defects can arise in any of these sectors at various times during the lifetime of the storage system (grown defects). Grown defects include, for example, invading foreign particles which become embedded onto the surface of the disc, or external shocks to the storage system which can cause the transducer to nick or crash onto the surface of the disc. Defective sectors present within a group of sectors storing any of the multiple copies of information pose either temporary or permanent problems in retrieving an entire copy.
In typical prior art systems, when retrieval of a first copy fails due to a defective sector being encountered, a second attempt is made to retrieve a second copy. If the second attempt fails, a third attempt is made to retrieve a third copy and so forth. This process is repeated until, either a complete copy of the data is retrieved or until a recovery attempt on the last available copy has failed. In this retrieval method, any portion of information contained on a defective sector in each copy is sufficient to prevent the retrieval of a complete copy of information. Therefore, at least one copy of information should be contained on a set of completely error-free sectors for the prior art retrieval method to work. Consequently, data can be lost, or in some cases, where critical information like the defect table cannot be retrieved, the drive could prevent the user from accessing any data stored on the disc.
However, as the user fills up the space on the disc with data there is less space available on the disc to store complete copies of the data. Therefore, in order to preserve as much space on the disc, error correction codes (ECC) are added to the data stored on the disc to assist in the recreation of corrupted data. The use of ECC on data then replaces the need for copying or mirroring of data to other sectors of the drive.
There are several types of error correction codes that have been developed for recovering lost data. Error correction methods are typically chosen depending on the error characteristics of the transmission or storage medium, such that these errors are detected and corrected with a minimum of redundant data stored or sent. Typically, in data storage systems, block ECC codes are used, such as Hamming codes or Reed-Solomon codes. These codes transform a chunk of bits into a longer chunk of bits in such a way that errors up to a threshold in each block of data can be detected and corrected. Hamming codes are typically used to correct errors that occur in the main memory such as DRAM, whereas Reed-Solomon code is typically used to correct errors in peripheral devices such as disc drives. However, either correction type can be used on either type of device.
Hamming codes allow for detection of multiple errors in the bits that comprise a word. A word is merely a set number of bits that represent data. Generally in prior art systems a word is an 8, 16 or 32 bit string. Hamming code is able to correct errors of one bit, but cannot correct errors of more than one bit in the word. The ability to correct a single bit in words of this length has provided sufficient reliability for the data. However, as word length has increased with the use of 64 and 128 bit words, there is an increase in the probability of errors occurring in the words, and therefore can increase the need for more error correction that cannot be provided by Hamming ECC.
Reed-Solomon coding has historically been used in areas where there is a high probability of errors occurring where multiple bits or even bytes of data are lost. Reed-Solomon code provides the ability to correct multiple errors as the error correction is applied to entire blocks of data.
Storage of Reed-Solomon ECC generally does not present a problem in peripheral storage systems because a small amount of data is written to the sector in addition to the actual data. In current generation disc drives a typical sector size is 512 bytes. Reed Solomon error correction code encodes blocks of n-bit symbols in the sector. The total number of n-bit symbols in the encoded block is 2n−1. Thus a block encoding 8 bit bytes has 255 bytes. The number of data symbols in the block can vary. A typical block encodes 233 bytes in the 255-byte block. This leaves 22 bytes in the block for error correction. The scheme encodes the block's message as points in a polynomial plotted over a finite field (usually a small binary number). The coefficients of the polynomial are the data of the block. The plot over determines the coefficients, which can be recovered from quite small subsets of the plotted points. In the same sense that one can correct a curve by interpolating past a gap, a Reed-Solomon code can bridge a series of errors in a block of data to recover the coefficients of the polynomial that drew the original curve.
As sector sizes increase and disc drives become more sensitive due to advances in storage technology, it is becoming more important to reconstruct corrupted data. As users typically don't use the entire capacity of the disc for storage there is a vast amount of unused space on the drive that can be used for data redundancy and error correction. Therefore, it is desirable to have a disc drive or other storage media that increases data redundancy without detracting from the overall capacity of the storage media.
Embodiments of the present invention provide solutions to these and other problems, and offer other advantages over the prior art.